/*
 * @Autor: taobo
 * @Date: 2020-06-21 10:37:52
 * @LastEditTime: 2020-06-29 13:42:47
 */ 
//求n个正整数构成的一个给定集合A = {a1,a2,a3,...,an}的子集，子集的和要等于一个给定的正整数d。请输出所有符合条件的子集。
// dest  src
// src    dest    n 
#include <bits/stdc++.h>
using namespace std;
class Subset
{
  vector<vector<int>> ans;
public:
void dfs(vector<int>& nums, vector<int>& subs,int d,int start,int sum)
{
  if(sum==d){
    ans.push_back(subs);
    return;
  }else if(sum>d || start==nums.size()){
    return;
  }
  for(int i=start;i<nums.size();++i){
    subs.push_back(nums[i]);
    dfs(nums,subs,d,i+1,sum+nums[i]);
    subs.pop_back();
  }
}
vector<vector<int>> subset(vector<int>& nums, int d)
{
    vector<int> subs;
    dfs(nums,subs,d,0,0);
    return ans;
}
};
//有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，
//每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法.
//1   2    3   4  
int allsolution(int n)
{
  if(n<=0) return 0;
  if(n==1) return 3;
  if(n==2 || n==3) return 6;
  vector<int> dp(n+1,0);
  dp[1] = 3;
  dp[2] = 6;
  dp[3] = 6;
  for(int i=4;i<n+1;++i)
  {
    dp[i] = dp[i-1] + dp[i-2]*2;
  }
  return dp[n];
}